package org.tau.workshop2011.semantics

import collection.immutable.{ SortedSet, TreeSet }
import collection.mutable.{LinkedList, Set => MutableSet, HashSet => MutableHashSet, LinkedHashMap => MutableLinkedHashMap}

/**
 * A class for maintaining a dependency list between components of the same
 * type. The class will throw an error whenever a cyclic dependency is
 * introduced into the system.
 *
 * The class can maintains track only of direct dependencies, but by calling the
 * expand method, it is possible to add all the indirect dependencies as direct
 * dependencies.
 *
 * In addition to tracking dependencies of the form "A depends on B", this class
 * also allows figuring out all the reverse-dependencies ("Who depends on B?").
 */
class DependencyTracker[T] {

  case class CyclicDependencyException(dependant:T)
    extends Exception (dependant + " depends on itself in/directly!")

  /* We want to have a deterministic result for the variable listing later, so
   * we will enforce some fixed order on the iterator of the keys of the map
   */
  val dependencies:MutableLinkedHashMap[T, MutableSet[T]] = new MutableLinkedHashMap

  def introduceComponent(component:T) {
    if (! (dependencies contains component))
      dependencies += component -> new MutableHashSet
  }

  def addDependency (dependant:T, dependency:T) {
    addDependencies(dependant, dependency :: Nil)
  }

  def addDependencies (dependant:T, newDependencies:Iterable[T]) {
    if (! (dependencies contains dependant))
      dependencies += dependant -> new MutableHashSet

    for (dependency <- newDependencies) {
      if (dependant == dependency)
        throw new CyclicDependencyException (dependant)

      if (! (dependencies contains dependency))
        dependencies += dependency -> new MutableHashSet

      dependencies(dependant) += dependency
    }
  }

  def expand() {
    var change = false
    do {
      change = false
      for (dependant <- dependencies.keys) {
        if (dependencies(dependant) contains dependant)
          throw new CyclicDependencyException (dependant)

        val newDependencies:MutableSet[T] = new MutableHashSet[T]
        for (dependency <- dependencies(dependant))
          newDependencies ++= dependencies(dependency)

        change |= ! ((newDependencies -- dependencies(dependant)).isEmpty)
        dependencies(dependant) ++= newDependencies
      }
    } while (change)
  }

  def dependenciesOf(dependant:T) : Set[T] = {
    Set () ++ dependencies(dependant)
  }

  def whoDependsOn(dependency:T) : Set[T] = {
    Set () ++ ((dependencies filter {
      case (dependent, hisDependencies) => hisDependencies contains dependency
    }).keys)
  }

  def getVars : Set[T] = {
    Set () ++ dependencies.keySet
  }

  def apply (dependency:T) : Set[T] = dependenciesOf (dependency)

  /**
   * This returns a list of all the dependencies sorted by their dependency
   * ordering, meaning a variable will only come after all of it's dependencies
   */
  def dependencySortedVars : Traversable[T] = {
    val resolved = new scala.collection.mutable.LinkedHashSet[T]
    val allVars = getVars
    var iteration = 1

    while (resolved.size != allVars.size) {
      for (variable <- getVars) {
        val deps = dependencies(variable)
        if (deps.size < iteration && (deps subsetOf resolved)) {
          resolved += variable
        }
      }
      iteration += 1
    }

    resolved
  }
}
